package chain;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 *
 *
 */
public class Solution_5 {

	// 思路1：借助哈希表
	public ListNode detectCycle(ListNode head) {
		Set<ListNode> set = new HashSet();
		ListNode node = head;
		while (node != null) { // 遍历链表中的每个节点
			if (set.contains(node)) { //一旦遇到了此前遍历过的节点，就可以判定链表中存在环
				return node;
			}
			set.add(node); // 记录链表的每个节点
			node = node.next; //移动指针
		}
		return null;
	}

	// 思路2：利用快慢指针，代码模板参考chain/Solution_3
	// 参考：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/xiang-xi-tu-jie-ken-ding-kan-de-ming-bai-by-xixili/
	public ListNode detectCycle2(ListNode head) {
		ListNode slow = head; // 慢指针
		ListNode fast = head; // 快指针
		// 如果有环，则快慢指针一定会相遇，因为每走1轮，fast 与 slow 的间距 +1，fast 终会追上slow
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;

			// 快慢指针相遇，说明循环
			if (slow == fast) {
				break;
			}
		}

		// 如果快指针为空或下一个节点为空，则说明无环
		if (fast == null || fast.next == null) {
			return null;
		}

		fast = head; //令其中一个指针指向head
		while (fast != slow) { // 两个指针同步往后移动，再次相遇即为环的起始点
			fast = fast.next;
			slow = slow.next;
		}

		return fast;
	}

	class ListNode {
		int val;
		ListNode next;
		ListNode(int x) {
			val = x;
		}
	}
}